package dp01;

/**
 * 题目：下降路径最小和
 * 题目链接：https://leetcode.cn/problems/minimum-falling-path-sum/description/
 */
public class Solution4 {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n+1][n+2];
//        for (int i = 0; i <= n+1; i++) {   //把第一行全部初始化为0（因为默认为0,所以可省略）
//            dp[0][i] = 0;
//        }
        for (int i = 1; i <= n ; i++) {       //第一列和最后一列为最大值，才不影响dp填空
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n ; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];
            }
        }
        //最后这一行都是到达该位置的最小下降路径和，所以需从中找到最小的
        int ret = Integer.MAX_VALUE;
        for (int i = 1; i <= n ; i++) {
            ret = Math.min(ret,dp[n][i]);
        }
        return ret;
    }
}
